﻿/*

Copyright (c) 2009, Stephen Remde
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in the
      documentation and/or other materials provided with the distribution.
    * Neither the name of the <organization> nor the
      names of its contributors may be used to endorse or promote products
      derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY STEPHEN REMDE ''AS IS'' AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL STEPHEN REMDE BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


*/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows;

namespace Graphs
{
    public class Graph
    {

        public Graph()
        {
        }
        public Graph(GraphCanvas c)
            : this()
        {
            this.c=c;
        }

        /// <summary>
        /// our links
        /// </summary>
        protected List<Link> Links = new List<Link>();

        /// <summary>
        /// our nodes
        /// </summary>
        protected List<Node> Nodes = new List<Node>();


        private object sync = new object();

        /// <summary>
        /// Organizes the layout
        /// </summary>
        /// <param name="iterations"></param>
        public void Organize(int iterations)
        {
            lock (sync)
            {
                for (int i = iterations; i > 0; i--)
                {
                    CalcRepel();
                    CalcAttract();
                    UpdateNodes();
                }
            }
        }

        private void UpdateNodes()
        {
            foreach (Node n in Nodes)
            {
                if (n.fixedinplace) // dont apply force 
                {
                    n.dx = 0;
                    n.dy = 0;
                }
                else
                {
                    n.x += n.dx * 4; // amplify force to speed up simulation
                    n.y += n.dy * 4;

                    n.dx *= 0.8f; // dampen 
                    n.dy *= 0.8f;
                }
            }
        }

        private void CalcAttract()
        {
            foreach (Link l in Links)
            {
                Node a = l.a;
                Node b = l.b;

                if ((!a.fixedinplace || !b.fixedinplace) && (a.visible || b.visible) && (l.visible || l.force_when_visible) )
                {
                    float dx = a.x - b.x;
                    float dy = a.y - b.y;

                    float distance2 = dx * dx + dy * dy;

                    if (distance2 > 0)
                    {
                        dx /= distance2;
                        dy /= distance2;

                        float distance = (float)Math.Sqrt(distance2);

                        distance = l.length - distance; // distance from desired length

                        distance = distance * l.strength;
                        dx *= distance;
                        dy *= distance;

                        // put force on paricles
                        if (a.fixedinplace || b.fixedinplace)
                        {
                            dx *= 2;
                            dy *= 2;
                        }

                        if (!a.fixedinplace)
                        {
                            a.dx += dx;
                            a.dy += dy;
                        }

                        if (!b.fixedinplace)
                        {
                            b.dx -= dx;
                            b.dy -= dy;
                        }
                    }
                }
            }
        }

        private void CalcRepel()
        {
            for (int i = 0; i < Nodes.Count; i++) //for each node
            {
                Node a = Nodes[i];

                if (!a.visible)
                    continue;

                for (int j = i + 1; j < Nodes.Count; j++) // against all over nodes
                {
                    Node b = Nodes[j];

                    if (!b.visible)
                        continue;

                    if (!a.fixedinplace || !b.fixedinplace)
                    {
                        float dx = a.x - b.x;
                        float dy = a.y - b.y;

                        float distance3 = (Math.Abs(dx * dx * dx) + Math.Abs(dy * dy * dy) - (a.node_radius + b.node_radius)) / 1000;

                        if (distance3 < 1)
                            distance3 = 1;

                        dx /= distance3; // cubed so we first convert to unit vector then divide by distance
                        dy /= distance3;


                        // put force on paricles
                        if (a.fixedinplace || b.fixedinplace)
                        {
                            dx *= 2;
                            dy *= 2;
                        }

                        if (!a.fixedinplace)
                        {
                            a.dx += dx;
                            a.dy += dy;
                        }

                        if (!b.fixedinplace)
                        {
                            b.dx -= dx;
                            b.dy -= dy;
                        }
                    }
                }

            }
        }



        public void AutoAdjustViewport(float width, float height, float smooth)
        {   
            lock (sync)
            {
                AutoAdjustViewport(width, height, smooth, Nodes);   
            }
        }

        public void AutoAdjustViewport(float width, float height, float smooth, IEnumerable<Node> fitto)
        {
            float minx, maxx, miny, maxy;
            float maxdx, maxdy;

            float idealx, idealy;

            minx = miny = float.MaxValue;
            maxx = maxy = float.MinValue;

            maxdx = maxdy = 0;

            foreach (var n in fitto)
            {
                if (n.visible)
                {
                    if (n.x > maxx) maxx = n.x;
                    if (n.x < minx) minx = n.x;
                    if (n.y > maxy) maxy = n.y;
                    if (n.y < miny) miny = n.y;
                }
            }

            idealx = (maxx + minx) / 2;
            idealy = (maxy + miny) / 2;

            foreach (var n in fitto)
            {
                if (n.visible)
                {
                    float dx = n.x - idealx;
                    float dy = n.y - idealy;

                    if (dx < 0) dx = -dx;
                    if (dy < 0) dy = -dy;

                    dx += n.node_radius + 4;
                    dy += n.node_radius + 4;


                    if (dx > maxdx) maxdx = dx;
                    if (dy > maxdy) maxdy = dy;
                }
            }


            maxdx = (width / maxdx / 2);
            maxdy = (height / maxdy / 2);

            float idealzoom = Math.Min(maxdx, maxdy);

            idealzoom *= .9f;

            if (idealzoom > 4) idealzoom = 4;


            Viewport.OffsetX = Viewport.OffsetX * smooth + -idealx * (1 - smooth);
            Viewport.OffsetY = Viewport.OffsetY * smooth + -idealy * (1 - smooth);
            Viewport.Zoom = Viewport.Zoom * smooth + idealzoom * (1 - smooth);
        }

        GraphCanvas c;

        public void UpdateCanvas()
        {
            lock (sync)
            {
                
                foreach (var n in Nodes)
                    n.UpdateUIElemet(c);

                foreach (var l in Links)
                    l.UpdateUIElemet();

            }
        }

        public void Translate(int dx, int dy)
        {
            lock (sync)
            {
                foreach (Node n in Nodes)
                {
                    n.x += dx;
                    n.y += dy;
                }
            }
        }

        public Node GetNode(string name)
        {
            lock (sync)
            {
                return Nodes.FirstOrDefault(n => n.text == name);
            }
        }

        Random r = new Random();
        public Node AddNode(Node n, Node hint)
        {
            n = AddNode(n);

            n.x = hint.x + r.Next(-100, 100);
            n.y = hint.y + r.Next(-100, 100);

            return n;
        }

        public Node AddNode(Node n)
        {
            Node exists = GetNode(n.text);
            
            if (exists == null)
            {
                lock (sync)
                {
                    Nodes.Add(n);
                }

                return n;

            }
            else
                return exists;
        }

        public Link AddLink(Link l)
        {
            Link exists = GetLink(l.a, l.b);

            if( exists == null )
            {
                lock (sync)
                {
                    Links.Add(l);
                }
                
                l.CreateNode(c.LayoutRoot);

                return l;

            }
            else
                return exists;
        }

        public Link GetLink(Node a, Node b)
        {
            lock (sync)
            {
                return Links.FirstOrDefault(l => (l.a == a && l.b == b) || (l.b == a && l.a == b));
            }
        }

        public Node[] GetNodes()
        {
            lock (sync)
            {
                return Nodes.ToArray();
            }
        }

        public Link[] GetLinks()
        {
            lock (sync)
            {
                return Links.ToArray();
            }
        }

        public Node[] GetNodesLinkedToNode(Node n)
        {
                List<Node> connected = new List<Node>();
            lock (sync)
            {

                foreach (var l in Links)
                {
                    if (l.a == n) connected.Add(l.b);
                    else if (l.b == n) connected.Add(l.a);
                }                
            }
            return connected.Distinct().ToArray();

        }

        public struct _Viewport
        {
            public float OffsetX { get; set; }
            public float OffsetY { get; set; }
            public float Zoom { get; set; }

            public TransformGroup GetRenderTransform()
            {
                var t = new TransformGroup();
                var tran = new TranslateTransform() { X = OffsetX, Y = OffsetY };
                var scal = new ScaleTransform() { ScaleX = Zoom, ScaleY = Zoom };
                t.Children.Add(tran);
                t.Children.Add(scal);
                return t;
            }
        }

        public _Viewport Viewport;


        internal void AutoAdjustViewport(float smooth, IEnumerable<Node> Fitto)
        {
            if (c.LayoutRoot.ActualHeight == 0 || c.LayoutRoot.ActualWidth == 0)
                return;

            if (Fitto == null)
            AutoAdjustViewport((float)c.LayoutRoot.ActualWidth, (float)c.LayoutRoot.ActualHeight, smooth);
            else
                AutoAdjustViewport((float)c.LayoutRoot.ActualWidth, (float)c.LayoutRoot.ActualHeight, smooth, Fitto);


            var t = Viewport.GetRenderTransform();
            t.Children.Add(new TranslateTransform() { X = c.LayoutRoot.ActualWidth / 2, Y = c.LayoutRoot.ActualHeight / 2 });
            c.LayoutRoot.RenderTransform = t; 
        }

        internal void AutoAdjustViewport(float smooth)
        {
            AutoAdjustViewport(smooth, null);    
        }
    }
}
